package com.jjlin.leetcode.biweekly_contest.no40_2020_11_28;

import java.util.Deque;
import java.util.LinkedList;

public class Solution3 {
    //设计前中后队列
    class FrontMiddleBackQueue {

        Deque<Integer> lq, rq; //左右两个双端队列
        //初始化队列
        public FrontMiddleBackQueue() {
            lq = new LinkedList<>();
            rq = new LinkedList<>();
        }

        //保证lq.size() == rq.size() or lq.size() + 1 == rq.size()
        public void adjust(){
            while(lq.size() > rq.size())
                rq.offerFirst(lq.pollLast());
            while(rq.size() > lq.size() + 1)
                lq.offerLast(rq.pollFirst());
        }

        //将val添加到队列的前面
        public void pushFront(int val) {
            lq.offerFirst(val);
            adjust();
        }

        //将val添加到队列的中间
        public void pushMiddle(int val) {
            lq.offerLast(val);
            adjust();
        }

        //将val添加到队列的后面
        public void pushBack(int val) {
            rq.offerLast(val);
            adjust();
        }

        //将最前面的元素从队列中删除并返回，如果队列为空，返回-1
        public int popFront() {
            if(rq.isEmpty())
                return -1;
            int res;
            if(!lq.isEmpty())
                res = lq.pollFirst();
            else
                res = rq.pollFirst();
            adjust();
            return res;
        }

        //将正中间的元素从队列中删除并返回，如果队列为空，返回-1
        public int popMiddle() {
            if(rq.isEmpty())
                return -1;
            int res;
            if(lq.size() == rq.size())
                res = lq.pollLast();
            else
                res = rq.pollFirst();
            adjust();
            return res;
        }

        //将最后面的元素从队列中删除并返回，如果队列为空，返回-1
        public int popBack() {
            if(rq.isEmpty())
                return -1;
            int res = rq.pollLast();
            adjust();
            return res;
        }
    }

}
